package medium.array;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/maximum-erasure-value">1695. 删除子数组的最大得分</a>
 * 给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
 * 返回 只删除一个 子数组可获得的 最大得分 。
 * 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
 * 示例 1：
 *   输入：nums = [4,2,4,5,6]
 *   输出：17
 *   解释：最优子数组是 [2,4,5,6]
 * 示例 2：
 *   输入：nums = [5,2,1,2,5,2,1,2,5]
 *   输出：8
 *   解释：最优子数组是 [5,2,1] 或 [1,2,5]
 * 提示：
 *   1 <= nums.length <= 100000
 *   1 <= nums[i] <= 10000
 * 解题思路：滑动窗口不断右移，保证窗口内的元素唯一，同时更新最大得分
 *   1.初始化滑动窗口左边界为数组下标0，右边界为数组下标1，最大得分为左边第一个元素值，同时定义一个临时最大值，初始为左边第一个元素值，用于和最大得分比较，大于最大得分则更新最大得分
 *   2.由于已知元素值最大不超过10000，因此可以利用一个大小10001的数组来存储元素是否存在于滑动窗口内，提升效率
 *   3.右边界从1开始不断右移，利用boolean数组判断右边元素是否已经存在于窗口内，若不存在，则将boolean数组对应下标（右边元素值）置为true表示该元素已存在，并更新临时最大值为临时最大值
 *     若存在，则左边界需要不断左移至存在元素的位置，每次左移都要更新临时最大值=临时最大值-左移的值
 *   4.每次右移一位，都需要用临时最大值和当前最大得分来比较，得出最大值，并更新最大得分
 *   5.当右边界移至数组尾部时，结束移动，返回最大得分即可
 * @author 刘学松
 * @date 2021-04-08 20:07
 */
public class 删除子数组的最大得分 {
    public static void main(String[] args) {
        int[] nums = {187, 470, 25, 436, 538, 809,
                441, 167, 477, 110, 275, 133, 666, 345, 411, 459, 490,
                266, 987, 965, 429, 166, 809,
                340, 467, 318, 125, 165, 809,
                610, 31, 585, 970, 306, 42, 189, 169, 743, 78, 810, 70, 382, 367, 490,
                787, 670, 476, 278, 775, 673, 299, 19, 893, 817, 971, 458, 409, 886, 434};
//        int[] nums = {1, 2, 1, 4};
        System.out.println(maximumUniqueSubarray(nums));
        System.out.println(Arrays.stream(nums).sum());
    }

    public static int maximumUniqueSubarray(int[] nums) {
        int max = nums[0];
        int max1 = max;
        int left = 0, right = 1;
        boolean[] booleans = new boolean[10001];
        booleans[max] = true;
        while (right < nums.length) {
            int rightNum = nums[right];
            if (!booleans[rightNum]) {
                max1 += rightNum;
                booleans[rightNum] = true;
            } else {
                booleans[rightNum] = false;
                while (booleans[nums[left]]) {
                    max1 -= nums[left];
                    booleans[nums[left]] = false;
                    left++;
                }
                booleans[rightNum] = true;
                ++left;
            }
            max = Math.max(max, max1);
            ++right;
        }
        return max;
    }
}
